package com.leetcode.根据数据结构分类.图;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2021/1/12
 * @description: 1203. 项目管理
 * https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/
 * 卧槽，太难了。看来数据结构中最难的就是树和图了，得再去缕一缕图啊！
 */
public class C_1203_项目管理 {

	public static void main(String[] args) {
		int n = 8;
		int m = 2;
		int[] group = new int[]{-1, -1, 1, 0, 0, 1, 0, -1};
		List<List<Integer>> beforeItems = new ArrayList<>();
		beforeItems.add(new ArrayList<>());
		beforeItems.add(Arrays.asList(6));
		beforeItems.add(Arrays.asList(5));
		beforeItems.add(Arrays.asList(6));
		beforeItems.add(Arrays.asList(3, 6));
		beforeItems.add(new ArrayList<>());
		beforeItems.add(new ArrayList<>());
		beforeItems.add(new ArrayList<>());

		C_1203_项目管理 action = new C_1203_项目管理();
		int[] res = action.sortItems(n, m, group, beforeItems);
		System.out.println("res = " + Arrays.toString(res));
	}

	/**
	 * 不懂题目里的 组 有什么意义。
	 * 1.遍历一遍，组装成 key:group - value:List(index)
	 * 对于 -1 的 group 添加到对应的
	 * 2.遍历 map ,进行DFS
	 * --
	 * 关于理解题意：如果有模糊的地方，就按照题目中最接近的意思套进去，有的时候其实是题意模糊了！
	 * --
	 * 实在是太难了，于是先CV了。
	 *
	 * @param n           项目的数量
	 * @param m           小组的数量
	 * @param group       项目和组的对应关系
	 * @param beforeItems
	 * @return
	 */
	public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
		//1.
		List<List<Integer>> groupItem = new ArrayList<List<Integer>>();
		for (int i = 0; i < n + m; ++i) {
			groupItem.add(new ArrayList<Integer>());
		}
		// 组间和组内依赖图
		//2.
		List<List<Integer>> groupGraph = new ArrayList<List<Integer>>();
		for (int i = 0; i < n + m; ++i) {
			groupGraph.add(new ArrayList<Integer>());
		}
		//3.
		List<List<Integer>> itemGraph = new ArrayList<List<Integer>>();
		for (int i = 0; i < n; ++i) {
			itemGraph.add(new ArrayList<Integer>());
		}

		// 组间和组内入度数组
		int[] groupDegree = new int[n + m];
		int[] itemDegree = new int[n];

		List<Integer> id = new ArrayList<Integer>();
		for (int i = 0; i < n + m; ++i) {
			id.add(i);
		}

		int leftId = m;
		// 给未分配的 item 分配一个 groupId
		for (int i = 0; i < n; ++i) {
			//如果项目没有分配组，就假设分配到一个独立的组中（索引 m 起始）
			if (group[i] == -1) {
				group[i] = leftId++;
			}
			//组名中添加 项目索引i
			groupItem.get(group[i]).add(i);
		}

		// 依赖关系建图 ?????
		for (int i = 0; i < n; ++i) {
			int curGroupId = group[i];
			for (int item : beforeItems.get(i)) {
				int beforeGroupId = group[item];
				if (beforeGroupId == curGroupId) {
					itemDegree[i] += 1;
					itemGraph.get(item).add(i);
				} else {
					groupDegree[curGroupId] += 1;
					groupGraph.get(beforeGroupId).add(curGroupId);
				}
			}
		}


		// 组间拓扑关系排序
		List<Integer> groupTopSort = topSort(groupDegree, groupGraph, id);
		if (groupTopSort.size() == 0) {
			return new int[0];
		}

		int[] ans = new int[n];
		int index = 0;
		// 组内拓扑关系排序
		for (int curGroupId : groupTopSort) {
			int size = groupItem.get(curGroupId).size();
			if (size == 0) {
				continue;
			}
			List<Integer> res = topSort(itemDegree, itemGraph, groupItem.get(curGroupId));
			if (res.size() == 0) {
				return new int[0];
			}
			for (int item : res) {
				ans[index++] = item;
			}
		}
		return ans;


	}

	public List<Integer> topSort(int[] deg, List<List<Integer>> graph, List<Integer> items) {
		Queue<Integer> queue = new LinkedList<Integer>();
		for (int item : items) {
			if (deg[item] == 0) {
				queue.offer(item);
			}
		}
		List<Integer> res = new ArrayList<Integer>();
		while (!queue.isEmpty()) {
			int u = queue.poll();
			res.add(u);
			for (int v : graph.get(u)) {
				if (--deg[v] == 0) {
					queue.offer(v);
				}
			}
		}
		return res.size() == items.size() ? res : new ArrayList<Integer>();
	}


}
